#include "gx_sort.h"
#include <stdlib.h>
#include <string.h>

static inline void change(void *a, void *b,int itemsize)
{
	char *c = (char*)a;
	char *d = (char*)b;
	//int tmp = *a;
	char *tmp = (char*)malloc(itemsize);
	memcpy(tmp,c,itemsize);
	memcpy(c,d,itemsize);
	memcpy(d,tmp,itemsize);
	free(tmp);
}

static inline void comeach(void *a,void *b,int itemsize,int(*compare)(const void *,const void *))
{
	if(compare(a,b) > 0)
	{
		change(a,b,itemsize);
	}
}

void shellsort(void*a,int num,int itemsize,int(*compare)(const void *,const void *))
{
	void*tmp =(void*)malloc(itemsize);
	char *b = (char*)a;
	int h;
	for(h=1;h <=num/9;h = 3*h+1)
		;

	for(;h>0;h/=3)
	{
		for(int i=h-1;i < num-1;i++)
		{
			memcpy(tmp,b+(i+1)*itemsize,itemsize);
			int j;
			for(j=i+1;j>h-1;j-=h)
			{
				if(compare(tmp,b+((j-1-(h-1))*itemsize))<0)
					memcpy(b+j*itemsize,b+((j-1-(h-1))*itemsize),itemsize);
				else
					break;
			}
			memcpy(b+j*itemsize,tmp,itemsize);
		}
	}
	free(tmp);
}

void isort(void* a,int num,int itemsize ,int (*compare)(const void *,const void *))
{
	void* tmp = (void*)malloc(itemsize);
	char *b = (char*)a;
	for(int i = 0; i < num-1;i++)
	{

		memcpy(tmp,b+itemsize*(i+1),itemsize);
		int j;
		for(j=i+1;j>0;j--)
		{
			if(compare(tmp,b+(j-1)*itemsize) < 0)
			{
				memcpy(b+j*itemsize,b+(j-1)*itemsize,itemsize);
			}
			else
				break;
		}
		memcpy(b+j*itemsize,tmp,itemsize);
	}
	free(tmp);
}

void ssort(void *a,int num,int itemsize,int(*compare)(const void *,const void *))
{
	int min;
	char *b = (char*)a;

	for(int i=0;i<num;i++)
	{
		min = i;
		for(int j=i+1;j<num;j++)
		{
			if(compare(b+min*itemsize,b+j*itemsize) > 0)
				min = j;
		}

		change(b+min*itemsize,b+i*itemsize,itemsize);
	}
}

void partition(void *b,int num,int itemsize,int (*compare)(const void*,const void *),int *n,int *m)
{
	if( num <= 0)
		return ;
	int i=0,j=num-2;
	int p=0,q=num-2;
	char *a = (char*)b;

	while( i<=j)
	{
		if(compare(a+i*itemsize,a+(num-1)*itemsize)>=0)
		{
			while(j>=0&&compare(a+j*itemsize,a+(num-1)*itemsize)>0)
			{
				j--;
			}

			if(j<i)
				break;

			change(a+i*itemsize,a+j*itemsize,itemsize);

			if(compare(a+i*itemsize,a+(num-1)*itemsize)==0)
			{
				change(a+i*itemsize,a+p*itemsize,itemsize);
				p++;
			}

			if(i != j)
			{
				if(compare(a+j*itemsize,a+(num-1)*itemsize) == 0)
				{
					change(a+j*itemsize,a+q*itemsize,itemsize);
					q--;
				}
			}
			j--;
		}
		i++;
	}

	change(a+i*itemsize,a+(num-1)*itemsize,itemsize);

	j = i+1;
	i = i-1;
	for(int k = 0;k<p;k++)
	{
		change(a+k*itemsize,a+i*itemsize,itemsize);
		i--;
	}

	for(int k=num-2;k>q;k--)
	{
		change(a+k*itemsize,a+j*itemsize,itemsize);
		j++;
	}

	*m = j;
	*n = i;

	return ;
}

void qqsort(void *a,int num,int itemsize,int (*compare)(const void *,const void *))
{
	if(num <= 9)
		return isort(a,num,itemsize,compare);

	char *b = (char*)a;
	change(b+num/2*itemsize,b+(num-2)*itemsize,itemsize);
	comeach(b,b+(num-2)*itemsize,itemsize,compare);
	comeach(b,b+(num-1)*itemsize,itemsize,compare);
	comeach(b+(num-1)*itemsize,b+(num-2)*itemsize,itemsize,compare);

	int m,n;
	partition(a,num,itemsize,compare,&m,&n);
	qqsort(a,m+1,itemsize,compare);
	qqsort((char*)a+n*itemsize,num-n,itemsize,compare);
}

static void merge(void *a,unsigned size,unsigned itemsize,unsigned mid,int (*compare)(const void *,const void *))
{
	char *tmp = (char*)malloc(size*itemsize);
	unsigned i=0,j=0,k=0;
	if(tmp == NULL)
		return;
	memset(tmp,0,size*itemsize);

	for(i=mid;i!=0;i--)
	{
		memcpy(tmp+itemsize*i,(char*)a+itemsize*i,itemsize);
	}

	memcpy(tmp+itemsize*i,(char*)a+itemsize*i,itemsize);
	for(j=mid+1;j<size;j++)
	{
		memcpy(tmp+itemsize*(size+mid-j),(char*)a+j*itemsize,itemsize);
	}

	i=0;
	j=size-1;

	for(k=0;k<size;k++)
	{
		if(compare(tmp+j*itemsize,tmp+i*itemsize)<0)
		{
			memcpy((char*)a+k*itemsize,tmp+j*itemsize,itemsize);
			j--;
		}
		else
		{
			memcpy((char*)a+k*itemsize,tmp+i*itemsize,itemsize);
		}
	}
	free(tmp);
}
void msort(void* a,unsigned size,unsigned itemsize,int (*compare)(const void *,const void *))
{
	int m = size/2;

	if(size%2 == 0)
	{
		m = size/2;
	}
	else
	{
		m = size/2+1;
	}

	if (size<=1)
		return ;

	msort(a,m,itemsize,compare);
	msort((char*)a+m*itemsize,size-m,itemsize,compare);
	merge(a,size,itemsize,m-1,compare);
}

/*
void msort_int(int a[],unsigned size)
{
	int m = size/2;

	if(size%2 == 0)
	{
		m = size/2;
	}
	else
	{
		m = size/2+1;
	}

	if (size<=1)
		return ;

	msort_int(a,m);
	msort_int(a+m,size-m);
	merge_int(a,size,m-1);
}

*/
/*
void merge_int(int a[],int size,unsigned mid)
{
	int *tmp = (int*)malloc(size*sizeof(int));
	int i=0,j=0,k=0;
	if(tmp == NULL)
		return;
	memset(tmp,0,size*sizeof(int));

	for(i=mid;i>=0;i--)
	{
		tmp[i]=a[i];
	}

	for(j=mid+1;j<size;j++)
	{
		tmp[size+mid-j]=a[j];
	}

	i=0;
	j=size-1;

	for(k=0;k<size;k++)
	{
		if(tmp[j]<tmp[i])
			a[k] = tmp[j--];
		else
			a[k] = tmp[i++];
	}
	free(tmp);
}
*/

/*
int* merge_int(int a[],int m,int b[],int n)
{
	int *c = (int*)malloc(sizeof(int)*(m+n));

	for(int i=0,j=0,k=0;i<n+m;i++)
	{
		if(j == m)
			c[i] = b[k++];
		else if(k == n)
			c[i] = a[j++];
		else
			c[i] = a[j]>b[k]?b[k++]:a[j++];
	}
	return c;
}
*/

/*
int partition_int(int a[],int num)
{
	if( num <= 0)
		return 0;
	int change;
	int i=0,j=num-2;

	while( i<=j)
	{
		if(a[i]>a[num-1])
		{
			while(j>=0&&a[j]>a[num-1])
			{
				j--;
			}

			if(j<i)
				break;

			change = a[i];
			a[i] = a[j];
			a[j] = change;
		}
		i++;
	}

	change = a[i];
	a[i] = a[num-1];
	a[num-1] = change;

	return i;
}

void qqsort_int(int a[],int num)
{
	if(num <= 1)
		return ;
	int i = partition_int(a,num);
	qqsort_int(a,i);
	qqsort_int(a+i+1,num-i-1);
}
*/

/*
void isort(int a[],int num)
{
	int tmp;
	for(int i = 0; i < num-1;i++)
	{

		tmp = a[i+1];
		int j;
		for(j=i+1;j>0;j--)
		{
			if(tmp < a[j-1])
				a[j] = a[j-1];
			else
				break;
		}
		a[j] = tmp;
	}
}
*/

/*
static inline void change_int(int *a, int *b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}
*/

/*
void ssort_int(int a[],int num)
{
	int min;

	for(int i=0;i<num;i++)
	{
		min = i;
		for(int j=i+1;j<num;j++)
		{
			if(a[min]>a[j])
				min = j;
		}

	//	tmp = a[min];
	//	a[min] = a[i];
	//	a[i] = tmp;
		change_int(&a[min],&a[i]);
	}
}
*/
/*
void partition_three_int(int a[],int num,int *n,int *m)
{
	if( num <= 0)
		return ;
	int change;
	int i=0,j=num-2;
	int p=0,q=num-2;

	while( i<=j)
	{
		if(a[i]>=a[num-1])
		{
			while(j>=0&&a[j]>a[num-1])
			{
				j--;
			}

			if(j<i)
				break;

			change = a[i];
			a[i] = a[j];
			a[j] = change;

			if(a[i] == a[num-1])
			{
				change = a[i];
				a[i] = a[p];
				a[p]=change;
				p++;
			}
			if(i != j)
			{
				if(a[j] == a[num-1])
				{
					change = a[j];
					a[j]= a[q];
					a[q] = change;
					q--;
				}
			}
			j--;
		}
		i++;
	}

	change = a[i];
	a[i] = a[num-1];
	a[num-1] = change;

	j = i+1;
	i = i-1;
	for(int k = 0;k<p;k++)
	{
		change = a[k];
		a[k] = a[i];
		a[i]=change;
		i--;
	}

	for(int k=num-2;k>q;k--)
	{
		change = a[k];
		a[k] = a[j];
		a[j] = change;
		j++;
	}

	*m = j;
	*n = i;

	return ;
}
*/

/*
int partition(void *b,int num,int itemsize,int (*compare)(const void *,const void *))
{
	if( num <= 0)
		return 0;

	int i=0,j=num-2;
	char *a = (char*)b;

	while( i<=j)
	{
		if(compare(a+i*itemsize,a+(num-1)*itemsize)>0)
		{
			while(j>=0&&compare(a+j*itemsize,a+(num-1)*itemsize)>0)
			{
				j--;
			}

			if(j<=i)
				break;
			change(a+i*itemsize,a+j*itemsize,itemsize);
		}
		i++;
	}

	change(a+i*itemsize,a+(num-1)*itemsize,itemsize);
	return i;
}
*/

/*
void qqsort(void *a,int num,int itemsize,int (*compare)(const void *,const void *))
{
	if(num <= 9)
		return isort(a,num,itemsize,compare);

	char *b = (char*)a;
	change(b+num/2*itemsize,b+(num-2)*itemsize,itemsize);
	comeach(b,b+(num-2)*itemsize,itemsize,compare);
	comeach(b,b+(num-1)*itemsize,itemsize,compare);
	comeach(b+(num-1)*itemsize,b+(num-2)*itemsize,itemsize,compare);

	int i = partition(a,num,itemsize,compare);
	qqsort(a,i,itemsize,compare);
	qqsort(b+itemsize*(i+1),num-i-1,itemsize,compare);
}
*/

/*
void qqsort_three_int(int a[],int num)
{
	if(num <= 1)
		return ;

	int m,n;
	partition_three_int(a,num,&m,&n);
	qqsort_three_int(a,m+1);
	qqsort_three_int(a+n,num-n);
}
*/
